SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Iterative compression</title>

</head>

Iterative compression

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Computer_science" title="Computer science">computer science</a>, iterative compression is an <a href="Algorithm" title="Algorithm">algorithmic</a> technique for the design of <a href="Parameterized_complexity" title="Parameterized complexity">fixed-parameter tractable algorithms</a>, in which one element (such as a <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex of a graph</a>) is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step.

The technique was invented by Reed, Smith and Vetta<a href="#cite_note-reed2004finding-1">[1]</a> to show that the problem of <a href="Odd_cycle_transversal" title="Odd cycle transversal">odd cycle transversal</a> was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle transversal number k. Odd cycle transversal is the problem of finding the smallest set of vertices of a graph that includes at least one vertex from every odd cycle; its parameterized complexity was a longstanding open question.<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> This technique later proved very useful in showing <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractability</a> results. It is now considered to be one of the fundamental techniques in the area of parameterized algorithmics.

Iterative compression has been used successfully in many problems, for instance <a href="Bipartite_graph#Odd_cycle_transversal" title="Bipartite graph">odd cycle transversal</a> (see below) and <a href="Bipartite_graph#Odd_cycle_transversal" title="Bipartite graph">edge bipartization</a>, <a href="Feedback_vertex_set" title="Feedback vertex set">feedback vertex set</a>, cluster vertex deletion and directed feedback vertex set.<a href="#cite_note-guo2009iterative-4">[4]</a> It has also been used successfully for exact <a href="Time_complexity#Exponential_time" title="Time complexity">exponential time algorithms</a> for <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">independent set</a>.<a href="#cite_note-fomin2010iterative-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Technique">Technique</h2></div>

Iterative compression applies, for instance, to parameterized <a href="Graph_theory" title="Graph theory">graph problems</a> whose inputs are a graph G = (V,E) and a <a href="Natural_number" title="Natural number">natural number</a> k, and where the problem is to test the existence of a solution (a set of vertices) of size ≤ k. Suppose

that the problem has the following properties:

<ul><li>It is closed under <a href="Induced_subgraph" title="Induced subgraph">induced subgraphs</a>: If a solution of size ≤ k exists in a given graph, then a solution of this size or smaller also exists in every induced subgraph).</li>

<li>If X is a solution, and X' is a set of vertices containing X, then X' is also a solution.</li>

<li>There exists an efficient subroutine which, given a solution Y of size k + 1 determines whether it can be compressed to a solution of size k. That is, it finds a solution of size k or determines that no such solution exists.</li></ul>

If these assumptions are met, then the problem can be solved by adding vertices one at a time to an induced subgraph, and finding the solution to the induced subgraph, as follows:

<ol><li>Start with a subgraph induced by a vertex set S of size k, and a solution X that equals S itself. (If X is not a solution to S then no solution exists.)</li>

<li>While S ≠ V, perform the following steps:

<ul><li>Let v be any vertex of V \ S, and add v to S</li>

<li>Test whether the (k + 1)-vertex solution Y = X ∪ {v} to S can be compressed to a k-vertex solution.</li>

<li>If it cannot be compressed, abort the algorithm: the input graph has no k-vertex solution.</li>

<li>Otherwise, set X to the new compressed solution and continue the loop.</li></ul></li></ol>

This algorithm calls the compression subroutine a linear number of times. Therefore, if the compression variant is solvable in fixed-parameter tractable time, i.e., f(k) · nc for some constant c, then the iterative compression procedure solving the entire problem runs in f(k) · nc+1 time.

The same technique can be applied to finding sets of edges for graph properties closed under subgraphs (rather than induced subgraph), or for other properties beyond graph theory. When the value of the parameter k is unknown, it can be found by using an outer level of <a href="Exponential_search" title="Exponential search">exponential search</a> or <a href="Sequential_search" class="mw-redirect" title="Sequential search">sequential search</a> for the optimal choice of k, with each step of the search based on the same iterative compression algorithm.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

In their original paper Reed et al. showed how to make a graph bipartite by deleting at most k vertices in time O(3k kmn). Later, a simpler algorithm was given, also using iterative compression, by Lokshstanov, Saurabh and Sikdar.<a href="#cite_note-lokshtanov2009simpler-6">[6]</a>

In order to compress a deletion set Y of size k + 1 to a deletion set X of size k, their algorithm tests all of the 3k+1 partitions of Y into three subsets: the subset of Y that belongs to the new deletion set, and the two subsets of Y that belong to the two sides of the bipartite graph that remains after deleting X. Once these three sets have been selected, the remaining vertices of a deletion set X (if it exists) can be found from them by applying a <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow min-cut</a> algorithm.

<a href="Vertex_cover" title="Vertex cover">Vertex cover</a> is another example for which iterative compression can be employed. In the vertex cover problem, a graph G = (V,E) and a natural number k are taken as inputs and the algorithm must decide whether there exists a set X of k vertices such that every edge is incident to a vertex in X. In the compression variant of the problem, the input is a set Y of k + 1 vertices that are incident to all edges of the graph, and the algorithm must find a set X of size k with the same property, if it exists. One way to do this is to test all 2k + 1 choices of which subset of Y is to be removed from the cover and reintroduced back into the graph. Such a choice can only work if no two removed vertices are adjacent, and for each such choice, the subroutine must include in the cover all the vertices outside Y that are incident to an edge that becomes uncovered by this removal. Using this subroutine in an iterative compression algorithm gives a simple O(2k n2) algorithm for vertex cover.

<ul><li><a href="Kernelization" title="Kernelization">Kernelization</a>, a different design technique for fixed-parameter tractable algorithms</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFReedSmithVetta2004" class="citation cs2"><a href="Bruce_Reed_(mathematician)" title="Bruce Reed (mathematician)">Reed, Bruce</a>; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.orl.2003.10.009">10.1016/j.orl.2003.10.009</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2057781">2057781</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFNiedermeier" class="citation cs2"><a href="Rolf_Niedermeier" title="Rolf Niedermeier">Niedermeier, Rolf</a>, Invitation to Fixed-Parameter Algorithms, Oxford University Press, p. 184, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780198566076</bdi></cite>

</li>

<cite id="CITEREFCyganFominKowalikLokshtanov2015" class="citation cs2">Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parameterized Algorithms, Springer, p. 555, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-21274-6</bdi></cite>.

</li>

<li id="cite_note-guo2009iterative-4"><a href="#cite_ref-guo2009iterative_4-0">^</a> <cite id="CITEREFGuoMoserNiedermeier2009" class="citation cs2">Guo, Jiong; Moser, Hannes; Niedermeier, Rolf (2009), "Iterative compression for exactly solving NP-hard minimization problems", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer, pp. 65–80, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-02094-0_4">10.1007/978-3-642-02094-0_4</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-02093-3</bdi></cite>.

</li>

<li id="cite_note-fomin2010iterative-5"><a href="#cite_ref-fomin2010iterative_5-0">^</a> <cite id="CITEREFFominGaspersKratschLiedloff2010" class="citation cs2">Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket (2010), "Iterative compression and exact algorithms", <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 411 (7): 1045–1053, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2009.11.012">10.1016/j.tcs.2009.11.012</a></cite>.

</li>

<li id="cite_note-lokshtanov2009simpler-6"><a href="#cite_ref-lokshtanov2009simpler_6-0">^</a> <cite id="CITEREFLokshtanovSaurabhSikdar2009" class="citation cs2">Lokshtanov, Daniel; Saurabh, Saket; Sikdar, Somnath (2009), "Simpler parameterized algorithm for OCT", 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers, Lecture Notes in Computer Science, vol. 5874, Springer, pp. 380–384, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-10217-2_37">10.1007/978-3-642-10217-2_37</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-10216-5</bdi></cite>.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-10-12" href="https://en.wikipedia.org/wiki/?title=Iterative_compression&oldid=1250833667">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>